package org.lql.algo.codecrush.week007;

/**
 * @author: liangqinglong
 * @date: 2025-08-18 23:21
 * @description: 4. 寻找两个正序数组的中位数 <a href="https://leetcode.cn/problems/median-of-two-sorted-arrays/description/">...</a>
 **/
public class FindMedianSortedArrays {

	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		int m = nums1.length;
		int n = nums2.length;
		int tot = m + n;
		if (tot % 2 == 1) {
			int mid = tot / 2 + 1;
			return findKth(nums1, m, nums2, n, mid);
		} else {
			int midLeft = tot / 2;
			int midRight = tot / 2 + 1;
			return (findKth(nums1, m, nums2, n, midLeft) + findKth(nums1, m, nums2, n, midRight)) / 2.0;
		}
	}

	private int findKth(int[] nums1, int m, int[] nums2, int n, int k) {
		int i = 0;
		int j = 0;
		while (true) {
			if (i == m) { // nums1 数组用完
				return nums2[j + k - 1];
			} else if (j == n) { // nums2 数组用完
				return nums1[i + k - 1];
			} else if (k == 1) { // 找到第 k 小的元素
				return Math.min(nums1[i], nums2[j]);
			}
			// 一般情况
			int half = k / 2;
			int newI = Math.min(i + half, m) - 1;
			int newJ = Math.min(j + half, n) - 1;
			int pivot1 = nums1[newI];
			int pivot2 = nums2[newJ];

			if (pivot1 <= pivot2) {
				k -= (newI - i + 1);
				i = newI + 1;
			} else {
				k -= (newJ - j + 1);
				j = newJ + 1;
			}
		}
	}

	public static void main(String[] args) {
		int[] nums1 = {1, 2};
		int[] nums2 = {3, 4};
		FindMedianSortedArrays findMedianSortedArrays = new FindMedianSortedArrays();
		System.out.println(findMedianSortedArrays.findMedianSortedArrays(nums1, nums2));
	}

}
